{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Valid Words for Each Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findNumOfValidWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猜字谜"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。</p>\n",
    "\n",
    "<p>字谜的迷面 <code>puzzle</code> 按字符串形式给出，如果一个单词 <code>word</code> 符合下面两个条件，那么它就可以算作谜底：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>单词 <code>word</code> 中包含谜面 <code>puzzle</code> 的第一个字母。</li>\n",
    "\t<li>单词 <code>word</code> 中的每一个字母都可以在谜面 <code>puzzle</code> 中找到。<br />\n",
    "\t例如，如果字谜的谜面是 \"abcdefg\"，那么可以作为谜底的单词有 \"faced\", \"cabbage\", 和 \"baggage\"；而 \"beefed\"（不含字母 \"a\"）以及 \"based\"（其中的 \"s\" 没有出现在谜面中）都不能作为谜底。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个答案数组 <code>answer</code>，数组中的每个元素 <code>answer[i]</code> 是在给出的单词列表 <code>words</code> 中可以作为字谜迷面 <code>puzzles[i]</code> 所对应的谜底的单词数目。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\n",
    "words = [\"aaaa\",\"asas\",\"able\",\"ability\",\"actt\",\"actor\",\"access\"], \n",
    "puzzles = [\"aboveyz\",\"abrodyz\",\"abslute\",\"absoryz\",\"actresz\",\"gaswxyz\"]\n",
    "<strong>输出：</strong>[1,1,3,2,4,0]\n",
    "<strong>解释：</strong>\n",
    "1 个单词可以作为 \"aboveyz\" 的谜底 : \"aaaa\" \n",
    "1 个单词可以作为 \"abrodyz\" 的谜底 : \"aaaa\"\n",
    "3 个单词可以作为 \"abslute\" 的谜底 : \"aaaa\", \"asas\", \"able\"\n",
    "2 个单词可以作为 \"absoryz\" 的谜底 : \"aaaa\", \"asas\"\n",
    "4 个单词可以作为 \"actresz\" 的谜底 : \"aaaa\", \"asas\", \"actt\", \"access\"\n",
    "没有单词可以作为 \"gaswxyz\" 的谜底，因为列表中的单词都不含字母 'g'。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= words.length <= 10^5</code></li>\n",
    "\t<li><code>4 <= words[i].length <= 50</code></li>\n",
    "\t<li><code>1 <= puzzles.length <= 10^4</code></li>\n",
    "\t<li><code>puzzles[i].length == 7</code></li>\n",
    "\t<li><code>words[i][j]</code>, <code>puzzles[i][j]</code> 都是小写英文字母。</li>\n",
    "\t<li>每个 <code>puzzles[i]</code> 所包含的字符都不重复。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-valid-words-for-each-puzzle](https://leetcode.cn/problems/number-of-valid-words-for-each-puzzle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-valid-words-for-each-puzzle](https://leetcode.cn/problems/number-of-valid-words-for-each-puzzle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"aaaa\",\"asas\",\"able\",\"ability\",\"actt\",\"actor\",\"access\"]\\n[\"aboveyz\",\"abrodyz\",\"abslute\",\"absoryz\",\"actresz\",\"gaswxyz\"]', '[\"apple\",\"pleas\",\"please\"]\\n[\"aelwxyz\",\"aelpxyz\",\"aelpsxy\",\"saelpxy\",\"xaelpsy\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        counterofword = collections.Counter()\n",
    "        # 1.统计word中每种模式的出现次数\n",
    "        res = []\n",
    "        for i in words: # acc  a:0;c:2 001|100|100 = 101\n",
    "            bitmask = 0\n",
    "            for j in i:\n",
    "                # 或，有1则为1\n",
    "                bitmask |= 1<<(ord(j) - ord(\"a\"))\n",
    "            counterofword[bitmask] += 1\n",
    "        \n",
    "        # 2.统计puzzles的子集\n",
    "        for curpuzzle in puzzles:\n",
    "            total = 0\n",
    "            for ch in self.subset(curpuzzle[1:]):\n",
    "                # 2.1 curpuzzle[0]的二进制表示\n",
    "                mask = 1<<(ord(curpuzzle[0]) - ord(\"a\"))\n",
    "                # 2.2 curpuzzle[0]+curpuzzle[1:]子集的二进制表示\n",
    "                for c in ch:\n",
    "                    mask |= 1<<(ord(c) - ord(\"a\"))\n",
    "                total += counterofword[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    def subset(self, words):\n",
    "        res = [\"\"]\n",
    "        for i in words:\n",
    "            res += [i + word for word in res]\n",
    "            print(res)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        m = len(puzzles)\n",
    "        cnt = Counter()\n",
    "        for i, word in enumerate(words):\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            cnt[mask] += 1\n",
    "        ans = [0] * m\n",
    "        for i, pz in enumerate(puzzles):\n",
    "            mask = 0\n",
    "            for c in pz:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            sub = mask\n",
    "            while sub:\n",
    "                if sub >> (ord(pz[0]) - ord('a')) & 1:\n",
    "                    ans[i] += cnt[sub]\n",
    "                sub = (sub - 1) & mask\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 状态压缩 + 子集\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            for perm in self.subsets(puzzle[1:]):\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    \n",
    "    def subsets(self, words: List[int]) -> List[List[int]]:\n",
    "        res = ['']\n",
    "        for i in words:\n",
    "            res = res + [i + word for word in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        num_words = []\n",
    "        for word in words:\n",
    "            num = 0\n",
    "            for w in word:\n",
    "                num |= 1 << (ord(w) - ord('a'))\n",
    "            num_words.append(num)\n",
    "\n",
    "        num_pu = []\n",
    "        for word in puzzles:\n",
    "            num = 0\n",
    "            for w in word:\n",
    "                num |= 1 << (ord(w) - ord('a'))\n",
    "            num_pu.append(num)\n",
    "        cnt_words = Counter(num_words)\n",
    "        ans = []\n",
    "\n",
    "        for i , x in enumerate(num_pu):\n",
    "            cnt = 0\n",
    "            for y , v in cnt_words.items():\n",
    "                if x | y == x and y & (1 << (ord(puzzles[i][0]) - ord('a'))):\n",
    "                    cnt += v\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        import collections\n",
    "        v_puzzles = [0] * len(puzzles)\n",
    "        v_words = collections.defaultdict(lambda: 0)\n",
    "        v_ans = [0] * len(puzzles)\n",
    "        a_v = ord('a')\n",
    "        for i, p in enumerate(puzzles):\n",
    "            v = 0\n",
    "            for c in p:\n",
    "                v = v | (1 << (ord(c) - a_v))\n",
    "            v_puzzles[i] = v\n",
    "        for i, w in enumerate(words):\n",
    "            v = 0\n",
    "            for c in w:\n",
    "                v = v | (1 << (ord(c) - a_v))\n",
    "            v_words[v] += 1\n",
    "\n",
    "        for i, v_p in enumerate(v_puzzles):\n",
    "            cnt = 0\n",
    "            for v_w, v_cnt in v_words.items():\n",
    "                if (v_p & v_w) == v_w and ((1 << (ord(puzzles[i][0]) - a_v)) & v_w) != 0:\n",
    "                    cnt += v_cnt\n",
    "            v_ans[i] = cnt\n",
    "        return v_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        #先处理 words\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "                # 统计具有相同模板的word有多少个，因为这里不涉及字母次数\n",
    "            freq[mask] += 1 \n",
    "\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            for perm in self.subsets(puzzle[1:]):#求子集\n",
    "                mask = 1<< (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    def subsets(self,words):\n",
    "        res = [\"\"]\n",
    "        for i in words:\n",
    "            res = res + [ i+ word for word in res ]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        ans = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            pres = [\"\"]\n",
    "            for i in puzzle[1:]:\n",
    "                pres = pres + [i + w for w in pres]\n",
    "            for p in pres:\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in p:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            ans.append(total)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        ans = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            pres = [\"\"]\n",
    "            for i in puzzle[1:]:\n",
    "                pres = pres + [i + w for w in pres]\n",
    "            for p in pres:\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in p:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            ans.append(total)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "            for perm in self.subsets(puzzle[1:]):\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n",
    "    \n",
    "    def subsets(self, words: List[int]) -> List[List[int]]:\n",
    "        res = [\"\"]\n",
    "        for i in words:\n",
    "            res = res + [i + word for word in res]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        frequency = collections.Counter()\n",
    "\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= (1 << (ord(ch) - ord(\"a\")))\n",
    "            if str(bin(mask)).count(\"1\") <= 7:\n",
    "                frequency[mask] += 1\n",
    "        \n",
    "        ans = list()\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "\n",
    "            # 枚举子集方法一\n",
    "            # for choose in range(1 << 6):\n",
    "            #     mask = 0\n",
    "            #     for i in range(6):\n",
    "            #         if choose & (1 << i):\n",
    "            #             mask |= (1 << (ord(puzzle[i + 1]) - ord(\"a\")))\n",
    "            #     mask |= (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "            #     if mask in frequency:\n",
    "            #         total += frequency[mask]\n",
    "\n",
    "            # 枚举子集方法二\n",
    "            mask = 0\n",
    "            for i in range(1, 7):\n",
    "                mask |= (1 << (ord(puzzle[i]) - ord(\"a\")))\n",
    "            \n",
    "            subset = mask\n",
    "            while subset:\n",
    "                s = subset | (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "                if s in frequency:\n",
    "                    total += frequency[s]\n",
    "                subset = (subset - 1) & mask\n",
    "            \n",
    "            # 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集\n",
    "            # 这里会漏掉空集，因此需要额外判断空集\n",
    "            if (1 << (ord(puzzle[0]) - ord(\"a\"))) in frequency:\n",
    "                total += frequency[1 << (ord(puzzle[0]) - ord(\"a\"))]\n",
    "\n",
    "            ans.append(total)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        frequency = collections.Counter()\n",
    "\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= (1 << (ord(ch) - ord(\"a\")))\n",
    "            if str(bin(mask)).count(\"1\") <= 7:\n",
    "                frequency[mask] += 1\n",
    "        \n",
    "        ans = list()\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "\n",
    "            # 枚举子集方法一\n",
    "            # for choose in range(1 << 6):\n",
    "            #     mask = 0\n",
    "            #     for i in range(6):\n",
    "            #         if choose & (1 << i):\n",
    "            #             mask |= (1 << (ord(puzzle[i + 1]) - ord(\"a\")))\n",
    "            #     mask |= (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "            #     if mask in frequency:\n",
    "            #         total += frequency[mask]\n",
    "\n",
    "            # 枚举子集方法二\n",
    "            mask = 0\n",
    "            for i in range(1, 7):\n",
    "                mask |= (1 << (ord(puzzle[i]) - ord(\"a\")))\n",
    "            \n",
    "            subset = mask\n",
    "            while subset:\n",
    "                s = subset | (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "                if s in frequency:\n",
    "                    total += frequency[s]\n",
    "                subset = (subset - 1) & mask\n",
    "            \n",
    "            # 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集\n",
    "            # 这里会漏掉空集，因此需要额外判断空集\n",
    "            if (1 << (ord(puzzle[0]) - ord(\"a\"))) in frequency:\n",
    "                total += frequency[1 << (ord(puzzle[0]) - ord(\"a\"))]\n",
    "\n",
    "            ans.append(total)\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.frequency = 0\n",
    "        self.child = dict()\n",
    "\n",
    "# 基于字典树的解法\n",
    "class Solution2:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        root = TrieNode()\n",
    "\n",
    "        def add(word: List[str]):\n",
    "            cur = root\n",
    "            for ch in word:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if idx not in cur.child:\n",
    "                    cur.child[idx] = TrieNode()\n",
    "                cur = cur.child[idx]\n",
    "            cur.frequency += 1\n",
    "\n",
    "        # 在回溯的过程中枚举 puzzle 的所有子集并统计答案\n",
    "        # find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）\n",
    "        # find 函数的返回值即为谜底的数量\n",
    "        def find(puzzle: List[str], required: str, cur: TrieNode, pos: int) -> int:\n",
    "            # 搜索到空节点，不合法，返回 0\n",
    "            if not cur:\n",
    "                return 0\n",
    "            # 整个 puzzle 搜索完毕，返回谜底的数量\n",
    "            if pos == 7:\n",
    "                return cur.frequency\n",
    "            \n",
    "            ret = 0\n",
    "            # 选择第 pos 个字母\n",
    "            if (idx := ord(puzzle[pos]) - ord(\"a\")) in cur.child:\n",
    "                ret += find(puzzle, required, cur.child[idx], pos + 1)\n",
    "\n",
    "            # 当 puzzle[pos] 不为首字母时，可以不选择第 pos 个字母\n",
    "            if puzzle[pos] != required:\n",
    "                ret += find(puzzle, required, cur, pos + 1)\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for word in words:\n",
    "            # 将 word 中的字母按照字典序排序并去重\n",
    "            word = sorted(set(word))\n",
    "            # 加入字典树中\n",
    "            add(word)\n",
    "\n",
    "        ans = list()\n",
    "        for puzzle in puzzles:\n",
    "            required = puzzle[0]\n",
    "            puzzle = sorted(puzzle)\n",
    "            ans.append(find(puzzle, required, root, 0))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        freq = collections.Counter()\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            freq[mask] += 1\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            pres = [\"\"]\n",
    "            for i in puzzle[1:]:\n",
    "                pres = pres + [i + w for w in pres]\n",
    "            total = 0\n",
    "            for perm in pres:\n",
    "                mask = 1 << (ord(puzzle[0]) - ord('a'))\n",
    "                for c in perm:\n",
    "                    mask |= 1 << (ord(c) - ord('a'))\n",
    "                total += freq[mask]\n",
    "            res.append(total)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        a_v = ord('a')\n",
    "        v_d = collections.Counter(map(lambda ws: sum(1 << (ord(c) - a_v) for c in ws), filter(lambda w: len(w) <= 7, map(frozenset, words))))\n",
    "        v_ans = [0] * len(puzzles)\n",
    "\n",
    "        for i, p in enumerate(puzzles):\n",
    "            cnt = 0\n",
    "            v_p = 0\n",
    "            for c in p:\n",
    "                v_p = v_p | (1 << (ord(c) - a_v))\n",
    "            for v_w, v_cnt in v_d.items():\n",
    "                if (v_p & v_w) == v_w and ((1 << (ord(puzzles[i][0]) - a_v)) & v_w) != 0:\n",
    "                    cnt += v_cnt\n",
    "            v_ans[i] = cnt\n",
    "        return v_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        frequency = collections.Counter()\n",
    "\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= (1 << (ord(ch) - ord(\"a\")))\n",
    "            if str(bin(mask)).count(\"1\") <= 7:\n",
    "                frequency[mask] += 1\n",
    "        \n",
    "        ans = list()\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "\n",
    "            # 枚举子集方法一\n",
    "            # for choose in range(1 << 6):\n",
    "            #     mask = 0\n",
    "            #     for i in range(6):\n",
    "            #         if choose & (1 << i):\n",
    "            #             mask |= (1 << (ord(puzzle[i + 1]) - ord(\"a\")))\n",
    "            #     mask |= (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "            #     if mask in frequency:\n",
    "            #         total += frequency[mask]\n",
    "\n",
    "            # 枚举子集方法二\n",
    "            mask = 0\n",
    "            for i in range(1, 7):\n",
    "                mask |= (1 << (ord(puzzle[i]) - ord(\"a\")))\n",
    "            \n",
    "            subset = mask\n",
    "            while subset:\n",
    "                s = subset | (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "                if s in frequency:\n",
    "                    total += frequency[s]\n",
    "                subset = (subset - 1) & mask\n",
    "            \n",
    "            # 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集\n",
    "            # 这里会漏掉空集，因此需要额外判断空集\n",
    "            if (1 << (ord(puzzle[0]) - ord(\"a\"))) in frequency:\n",
    "                total += frequency[1 << (ord(puzzle[0]) - ord(\"a\"))]\n",
    "\n",
    "            ans.append(total)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        frequency = collections.Counter()\n",
    "\n",
    "        for word in words:\n",
    "            mask = 0\n",
    "            for ch in word:\n",
    "                mask |= (1 << (ord(ch) - ord(\"a\")))\n",
    "            if str(bin(mask)).count(\"1\") <= 7:\n",
    "                frequency[mask] += 1\n",
    "        \n",
    "        ans = list()\n",
    "        for puzzle in puzzles:\n",
    "            total = 0\n",
    "\n",
    "            # 枚举子集方法一\n",
    "            # for choose in range(1 << 6):\n",
    "            #     mask = 0\n",
    "            #     for i in range(6):\n",
    "            #         if choose & (1 << i):\n",
    "            #             mask |= (1 << (ord(puzzle[i + 1]) - ord(\"a\")))\n",
    "            #     mask |= (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "            #     if mask in frequency:\n",
    "            #         total += frequency[mask]\n",
    "\n",
    "            # 枚举子集方法二\n",
    "            mask = 0\n",
    "            for i in range(1, 7):\n",
    "                mask |= (1 << (ord(puzzle[i]) - ord(\"a\")))\n",
    "            \n",
    "            subset = mask\n",
    "            while subset:\n",
    "                s = subset | (1 << (ord(puzzle[0]) - ord(\"a\")))\n",
    "                if s in frequency:\n",
    "                    total += frequency[s]\n",
    "                subset = (subset - 1) & mask\n",
    "            \n",
    "            # 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集\n",
    "            # 这里会漏掉空集，因此需要额外判断空集\n",
    "            if (1 << (ord(puzzle[0]) - ord(\"a\"))) in frequency:\n",
    "                total += frequency[1 << (ord(puzzle[0]) - ord(\"a\"))]\n",
    "\n",
    "            ans.append(total)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        words_count = Counter(self.word_to_int(x) for x in words)\n",
    "        rst = [0] * len(puzzles)\n",
    "        for i in range(len(puzzles)):\n",
    "            puzzle_subsets = self.subsets(puzzles[i])\n",
    "            for puzzle_subset in puzzle_subsets:\n",
    "                rst[i] += words_count[puzzle_subset]\n",
    "        return rst\n",
    "        \n",
    "    def word_to_int(self, word: str) -> int:\n",
    "        rst = 0\n",
    "        for ch in word:\n",
    "            rst = rst | (1 << (ord(ch) - ord('a')))\n",
    "        return rst\n",
    "\n",
    "    def subsets(self, word: str) -> List[int]:\n",
    "        first_ch_int = 1 << (ord(word[0]) - ord('a'))\n",
    "        rst = []\n",
    "        for i in range(0, len(word)):\n",
    "            \n",
    "            for x in combinations(word[1:], i):\n",
    "                word_rst = first_ch_int\n",
    "                for x1 in x:\n",
    "                    word_rst = word_rst | (1 << (ord(x1) - ord('a')))\n",
    "                rst.append(word_rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        d = collections.Counter(filter(lambda w: len(w) <= 7, map(frozenset, words))) #改成了过滤函数\n",
    "        def f(p):\n",
    "            cbt = [p[0]]\n",
    "            for c in p[1: ]:\n",
    "                cbt += [s + c for s in cbt]\n",
    "            return sum(d[s] for s in map(frozenset, cbt) if s in d)\n",
    "        return [*map(f, puzzles)]\n",
    "\n",
    "# 作者：typingMonkey\n",
    "# 链接：https://leetcode.cn/problems/number-of-valid-words-for-each-puzzle/solutions/24712/5176-cai-zi-mi-pai-xu-hou-ha-xi-bi-jiao-by-tuotuol/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        d = collections.Counter(''.join(sorted({*w})) for w in words if len({*w}) <= 7)   #把谜底去重排序并合并计数\n",
    "        def f(p):\n",
    "            cbt = [p[0]]            #谜面首元素必须放进组合\n",
    "            for c in p[1: ]:        #谜面除首元素外，其他元素0-1状态放进组合排好序，以匹配处理后的谜底\n",
    "                cbt += [''.join(sorted(s + c)) for s in cbt]\n",
    "            return sum(d[s] for s in cbt if s in d) #如果谜面可以匹配谜底，就加上这种类型的谜底的数量\n",
    "        return [*map(f, puzzles)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.frequency = 0\n",
    "        self.child = dict()\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        root = TrieNode()\n",
    "\n",
    "        def add(word: List[str]):\n",
    "            cur = root\n",
    "            for ch in word:\n",
    "                idx = ord(ch) - ord(\"a\")\n",
    "                if idx not in cur.child:\n",
    "                    cur.child[idx] = TrieNode()\n",
    "                cur = cur.child[idx]\n",
    "            cur.frequency += 1\n",
    "\n",
    "        # 在回溯的过程中枚举 puzzle 的所有子集并统计答案\n",
    "        # find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）\n",
    "        # find 函数的返回值即为谜底的数量\n",
    "        def find(puzzle: List[str], required: str, cur: TrieNode, pos: int) -> int:\n",
    "            # 搜索到空节点，不合法，返回 0\n",
    "            if not cur:\n",
    "                return 0\n",
    "            # 整个 puzzle 搜索完毕，返回谜底的数量\n",
    "            if pos == 7:\n",
    "                return cur.frequency\n",
    "            \n",
    "            ret = 0\n",
    "            # 选择第 pos 个字母\n",
    "            if (idx := ord(puzzle[pos]) - ord(\"a\")) in cur.child:\n",
    "                ret += find(puzzle, required, cur.child[idx], pos + 1)\n",
    "\n",
    "            # 当 puzzle[pos] 不为首字母时，可以不选择第 pos 个字母\n",
    "            if puzzle[pos] != required:\n",
    "                ret += find(puzzle, required, cur, pos + 1)\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        for word in words:\n",
    "            # 将 word 中的字母按照字典序排序并去重\n",
    "            word = sorted(set(word))\n",
    "            # 加入字典树中\n",
    "            add(word)\n",
    "\n",
    "        ans = list()\n",
    "        for puzzle in puzzles:\n",
    "            required = puzzle[0]\n",
    "            puzzle = sorted(puzzle)\n",
    "            ans.append(find(puzzle, required, root, 0))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = dict()\n",
    "        self.end = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        n = len(puzzles)\n",
    "        ans = []\n",
    "        head = Trie()\n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in sorted(list(set(word))):\n",
    "                if c not in cur.next:\n",
    "                    cur.next[c] = Trie()\n",
    "                cur = cur.next[c]\n",
    "            cur.end += 1\n",
    "        for puzzle in puzzles:\n",
    "            f = puzzle[0]\n",
    "            puzzle = sorted(list(set(puzzle)))\n",
    "            l = len(puzzle)\n",
    "            res = 0\n",
    "            flag = False\n",
    "            def search(idx, cur):\n",
    "                nonlocal res\n",
    "                nonlocal flag\n",
    "                if cur.end > 0 and flag:\n",
    "                    res += cur.end\n",
    "                    cur.end = -cur.end\n",
    "                if idx > l - 1:\n",
    "                    if cur.end < 0:\n",
    "                        cur.end = -cur.end\n",
    "                    return\n",
    "                if len(cur.next) == 0:\n",
    "                    if cur.end < 0:\n",
    "                        cur.end = -cur.end\n",
    "                    return\n",
    "                w = puzzle[idx]\n",
    "                if w in cur.next:\n",
    "                    if w == f:\n",
    "                        flag = True\n",
    "                    search(idx + 1, cur.next[w])\n",
    "                    if w == f:\n",
    "                        flag = False\n",
    "                search(idx + 1, cur)\n",
    "            search(0, head)\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = dict()\n",
    "        self.end = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        n = len(puzzles)\n",
    "        ans = []\n",
    "        head = Trie()\n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in sorted(list(set(word))):\n",
    "                if c not in cur.next:\n",
    "                    cur.next[c] = Trie()\n",
    "                cur = cur.next[c]\n",
    "            cur.end += 1\n",
    "        for puzzle in puzzles:\n",
    "            f = puzzle[0]\n",
    "            puz = sorted(list(set(puzzle)))\n",
    "            l = len(puz)\n",
    "            res = 0\n",
    "            flag = False\n",
    "            def search(idx, cur):\n",
    "                nonlocal res\n",
    "                nonlocal flag\n",
    "                if cur.end > 0 and flag:\n",
    "                    res += cur.end\n",
    "                    cur.end = -cur.end\n",
    "                if idx > l - 1:\n",
    "                    if cur.end < 0:\n",
    "                        cur.end = -cur.end\n",
    "                    return\n",
    "                if len(cur.next) == 0:\n",
    "                    if cur.end < 0:\n",
    "                        cur.end = -cur.end\n",
    "                    return\n",
    "                w = puz[idx]\n",
    "                if w in cur.next:\n",
    "                    if w == f:\n",
    "                        flag = True\n",
    "                    search(idx + 1, cur.next[w])\n",
    "                    if w == f:\n",
    "                        flag = False\n",
    "                search(idx + 1, cur)\n",
    "            search(0, head)\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node():\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.cnt = 0\n",
    "\n",
    "class Tree():\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    def add(self, arr):\n",
    "        cur = self.root\n",
    "        for x in arr:\n",
    "            if x:\n",
    "                if not cur.left:\n",
    "                    cur.left = Node()\n",
    "                cur = cur.left\n",
    "                cur.cnt += 1\n",
    "            else:\n",
    "                if not cur.right:\n",
    "                    cur.right = Node()\n",
    "                cur = cur.right\n",
    "                cur.cnt += 1\n",
    "    def query(self, arr):\n",
    "        res = 0\n",
    "        cur = self.root\n",
    "        def dfs(index, cur):\n",
    "            if index == 26:\n",
    "                nonlocal res\n",
    "                res += cur.cnt\n",
    "                return None\n",
    "            if arr[index] == 0 and cur.left:\n",
    "                dfs(index+1, cur.left)\n",
    "            elif arr[index] == 1 and cur.right:\n",
    "                dfs(index+1, cur.right)\n",
    "            elif arr[index] == 2:\n",
    "                if cur.left:\n",
    "                    dfs(index+1, cur.left)\n",
    "                if cur.right:\n",
    "                    dfs(index+1, cur.right)\n",
    "        dfs(0, cur)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        tree = Tree()\n",
    "        for word in words:\n",
    "            arr = [False]*26\n",
    "            for x in word:\n",
    "                arr[ord(x)-ord('a')] = True\n",
    "            tree.add(arr)\n",
    "        res = []\n",
    "        for puzzle in puzzles:\n",
    "            arr = [1]*26\n",
    "            arr[ord(puzzle[0])-ord('a')] = 0\n",
    "            for x in puzzle[1:]:\n",
    "                arr[ord(x)-ord('a')] = 2\n",
    "            res.append(tree.query(arr))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        m = len(puzzles)\n",
    "        cnt = defaultdict(int)\n",
    "        for i, word in enumerate(words):\n",
    "            mask = 0\n",
    "            for c in word:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            cnt[mask] += 1\n",
    "        ans = [0] * m\n",
    "        for i, pz in enumerate(puzzles):\n",
    "            mask = 0\n",
    "            for c in pz:\n",
    "                mask |= 1 << (ord(c) - ord('a'))\n",
    "            sub = mask\n",
    "            while sub:\n",
    "                if sub >> (ord(pz[0]) - ord('a')) & 1:\n",
    "                    ans[i] += cnt[sub]\n",
    "                sub = (sub - 1) & mask\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
